Many real-world signals, such as textual, visual, audio, and financial data, lie near some low-dimensional subspace. That is, the matrices constructed using these observations (referred to herein as observed data matrices) as column vectors are often of relatively low rank, and thus data of many such real-world signals can be approximated by matrices whose ranks are much smaller than their column and row lengths (i.e., low-rank matrix approximations of observed data matrices). Accordingly, low-rank matrix approximation, wherein the fit between a given observed data matrix and an approximation matrix is minimized, may be used for mathematical modeling, data compression, etc. with respect to the data of such signals. The purpose of low-rank matrix approximation is to extract the low-dimensional subspaces or principal components of the observed data matrices constructed from the signals. Such low-rank matrix approximation has, for example, been a core task in many important areas including dimensionality reduction, computer vision, machine learning and signal processing, especially with high-dimensional datasets.
Principal component analysis (PCA) is a standard tool to seek the best low-rank representation of a given observation data matrix in the least squares (l2-norm) space. PCA, which can be computed via truncated singular value decomposition (SVD), is a linear transformation that rigidly rotates the coordinates of a given set of data, so as to maximize the variance of the data in each of the new dimensions in succession. As a result, using PCA, it is possible to describe the data in a lower-dimensional space, retaining only the first few principal components, and discarding the rest. However, conventional PCA does not work well in the presence of impulsive noise (e.g., non-Gaussian disturbances) and/or outliers in the observation data matrix. This is because the design of conventional PCA techniques utilizes least squares or the l2-norm minimization with respect to the observation data matrix, and the SVD cannot be generalized to the lp-norm except for p=2, indicating that such conventional PCA (referred to herein as l2-PCA) techniques are well suited only for additive Gaussian noise.
An existing method for robust low-rank matrix approximation is alternating convex optimization (ACO). In the ACO, the objective function is minimized over one factored matrix while the other factor is fixed in an iterative manner. Subspace estimation performance of the ACO is less than desired and computational complexity of the ACO is high. Accordingly, the use of ACO for robust low-rank matrix approximation is unsatisfactory with respect to some scenarios.
As can be appreciated from the foregoing, existing solutions for providing low-rank approximation of observed data matrices, such as PCA, are not robust with respect to impulsive noise and outlier points in the observed data matrix. The existing solutions for providing robust low-rank approximation of observed data matrices, such as ACO, can work in the impulsive noise environments but it is more computationally demanding and have somewhat poor performance in subspace estimation.